package com.LeeCode;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 数组中的第K个最大的元素
 */

public class Code215 {
    public static void main(String[] args) {
        int[] nums = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        System.out.println(new Code215().findKthLargest1(nums, 4));
    }

    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }

    public int findKthLargest1(int[] nums, int k) {
        int n = nums.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapfy(nums, n, i);
        }

        for (int i = 1; i <= k; i++) {
            swap(nums, 0, n - i);
            heapfy(nums, n - i, 0);
        }
        return nums[n - k];
    }

    public void heapfy(int[] nums, int heapSize, int rootIndex) {
        int largest = rootIndex;
        int leftChild = 2 * rootIndex + 1;
        int rightChild = 2 * rootIndex + 2;

        if (leftChild < heapSize && nums[leftChild] > nums[largest]) {
            largest = leftChild;
        }
        if (rightChild < heapSize && nums[rightChild] > nums[largest]) {
            largest = rightChild;
        }
        if (largest != rootIndex) {
            swap(nums, largest, rootIndex);
            heapfy(nums, heapSize, largest);
        }
    }

    public void swap(int[] nums, int i, int j) {
        int tmp;
        tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
